import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

class MyStack {

    Queue<Integer> queue1;
    Queue<Integer> queue2;


    public MyStack() {
        queue1 = new ArrayDeque<>();
        queue2 = new ArrayDeque<>();
    }

    public void push(int x) {
        if(!queue1.isEmpty()) {
            queue1.offer(x);
        }else if(!queue2.isEmpty()) {
            queue2.offer(x);
        }else {
            //两个都为空,指定放在queue1中
            queue1.offer(x);
        }
    }

    public int pop() {
        int i = 0;
        if(queue2.isEmpty()) {
            int size = queue1.size();
            for(i = 0; i < size- 1; i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }else {
            int size = queue2.size();
            for(i = 0; i < size- 1; i++) {
                queue1.offer(queue2.poll());
            }
            return  queue2.poll();
        }

    }

    public int top() {
        int i = 0;
        if(queue2.isEmpty()) {
            int size = queue1.size();
            for(i = 0; i < size- 1; i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.peek();
        }else {
            int size = queue2.size();
            for(i = 0; i < size- 1; i++) {
                queue1.offer(queue2.poll());
            }
            return  queue2.peek();
        }

    }

    public boolean empty() {
        //两个队列均为空的时候才能判断该栈为空
        return queue1.isEmpty() && queue2.isEmpty();
    }
}
class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        minStack = new Stack<>();
        stack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if(minStack.empty()) {
            minStack.push(val);
        }else {
            if(val <= minStack.peek()) {
                minStack.push(val);
            }
        }
    }

    public void pop() {
        int x = stack.pop();
        if(!minStack.empty()) {
            if(x == minStack.peek()) {
                minStack.pop();
            }
        }
    }

    //获取的普通栈的栈顶元素
    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}
public class test {
    public static boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushV.length; i++) {
            stack1.push(pushV[i]);
            while((!stack1.empty()) && (stack1.peek() == popV[j])) {
                //往stack11中入元素
                int get = stack1.pop();
                stack2.push(get);
                j++;

            }
        }
        return stack1.empty();
    }


    public static void main3(String[] args) {
        int[] push = {1,2,3,4,5};
        int[] pop = {4,5,3,2,1};
        System.out.println(IsPopOrder(push, pop));
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        minStack.getMin();
        minStack.pop();
        minStack.top();
        minStack.getMin();
    }
}
